package divide;

public class Hanio {
    public void hanio(int n,char A,char B,char C){
        if(n==1){
            System.out.println(A+"-->"+C);
        }else{
            hanio(n-1,A,C,B);
            System.out.println(A+"-->"+C);
            hanio(n-1,B,A,C);
        }
    }
    void merge(int [] arr,int mid,int l,int r){
        int []r1 = new int[r];
        int i = l,j=mid+1,k=l;
        while(i<=mid&&j<=r){
            if(arr[i]<=arr[j])
                r1[k++]=arr[i++];
            else{
                r1[k++] = arr[j++];
            }
        }
        while(i<=mid){
            r1[k++] = arr[i++];
        }
        while(j<=r){
            r1[k++] = arr[j++];
        }
        for(i = l;i<=r;i++)
            arr[i] = r1[i];
    }
    void mergesort(int arr[],int l,int r){
        if(l==r){
            return;
        }
        int mid = (l+r)/2;
        mergesort(arr,l,mid);
        mergesort(arr,mid+1,r);
        merge(arr,mid,l,r);
    }
    int pattion(int r[],int first,int end){
        int temp;
        int i  =first;
        int  j = end;
        while(i<j){
            while(i<j&&r[i]<=r[j])j--;
            if(i<j){
                temp = r[i];
                r[i] = r[j];
                r[j] = temp;
                i++;
            }
            while(i<j&&r[i]<=r[j]) i++;
            if(i<j){
                temp = r[i];
                r[i] = r[j];
                r[j] = temp;
                j--;
            }
        }
        return i;
    }
    void quickSort(int r[],int first,int end){
        if(first<end){
            int pivot = pattion(r,first,end);
            quickSort(r,first,pivot-1);
            quickSort(r,pivot+1,end);
        }
    }
    int MaxSum(int a[],int left,int right)
    {
        int sum = 0;int midSum = 0,leftSum = 0,rightSum = 0;
        int i ,center,s1,s2,lefts,rights;
        if(left == right)
            sum = a[left];
        else{
            center = (left + right)/2;
            leftSum = MaxSum(a,left,center);
            rightSum = MaxSum(a,center+1,right);
            s1 = 0;
            lefts = 0;
            for(i = center;i>=left;i--){
                lefts+=a[i];
                if(lefts>s1) s1 = lefts;
            }
            s2 = 0;
            rights = 0;
            for(i = center + 1;i<=right;i++){
                rights += a[i];
                if(rights > s2) s2 = rights;
            }
            midSum = s1+s2;
            if(midSum<leftSum) sum = leftSum;
            else sum = midSum;
            if(sum<rightSum) sum = rightSum;
        }
        return sum;
    }
}
class Main{
    public static void main(String[] args) {
        Hanio h = new Hanio();
        h.hanio(3,'a','b','c');
    }
}
